package com.demo.example.hot100;
//定义链表
class ListNode{
    public int val;
    public ListNode next;
    public ListNode(int val){
        this.val=val;
    }
}
public class TheSumOfTwoNums {
    public static void main(String[] args) {
        ListNode l1=new ListNode(9);
        l1.next=new ListNode(9);
        l1.next.next=new ListNode(9);
        l1.next.next.next=new ListNode(9);
        ListNode l2=new ListNode(9);
        l2.next=new ListNode(9);
        l2.next.next=new ListNode(9);
        l2.next.next.next=new ListNode(9);
        l2.next.next.next.next=new ListNode(9);
        l2.next.next.next.next.next=new ListNode(9);
        l2.next.next.next.next.next.next=new ListNode(9);
        addTwoNumbers(l1,l2);
    }
    //l1=9 9 9 9 9 9 9 9
    //l2=9 9 9 9
    //su=8 9 9 9 0 0 0  0 1
    public static ListNode addTwoNumbers(ListNode l1,ListNode l2){
        if(l1.val==0 && l1.next==null){
            return l2;
        }
        if(l2.val==0 && l2.next==null){
            return l1;
        }
        ListNode cur1=l1;
        ListNode cur2=l2;
        ListNode res=new ListNode((cur1.val+cur2.val)%10);
        ListNode cur=res;
        int did=(cur1.val+cur2.val)/10; //第一项的进位数
        cur1=cur1.next;
        cur2=cur2.next;
        while(cur1!=null  && cur2!=null){
            int sum=cur1.val+cur2.val+did;
            ListNode tmp=new ListNode(sum%10);
            cur.next=tmp;
            cur=cur.next;
            did=sum/10;
            cur1=cur1.next;
            cur2=cur2.next;
        }
        while(cur1!=null){
            int sum=cur1.val+did;
            ListNode tmp=new ListNode(sum%10);
            did=sum/10;
            cur1=cur1.next;
            cur.next=tmp;
            cur=cur.next;
        }
        while(cur2!=null){
            int sum=cur2.val+did;
            ListNode tmp=new ListNode(sum%10);
            did=sum/10;
            cur.next=tmp;
            cur2=cur2.next;
            cur=cur.next;
        }
        if(did!=0){
            ListNode tmp=new ListNode(did);
            cur.next=tmp;
        }
        return res;
    }
}
